import java.util.HashMap;
import java.util.Stack;

public class TreeNode {
    TreeNode right = null;
    TreeNode left = null;
    int val = 0;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode() {
    }

    public static String serialize(TreeNode root) {
        Stack<TreeNode> preOrder = new Stack<>();
        Stack<TreeNode> midOrder = new Stack<>();
        HashMap<Integer, Integer> numberMap = new HashMap<>();
        TreeNode nowNode;

        preOrder.push(root);
        String preOrderString = "";
        while (!preOrder.isEmpty()) {
            nowNode = preOrder.pop();
            numberMap.put(nowNode.val, numberMap.getOrDefault(nowNode.val, -1) + 1);
            if (nowNode.val >= 0) {
                nowNode.val += numberMap.get(nowNode.val) * 1024;
            } else {
                nowNode.val -= numberMap.get(nowNode.val) * 1024;
            }
            preOrderString = preOrderString + nowNode.val + "-";
            if (nowNode.right != null)
                preOrder.push(nowNode.right);
            if (nowNode.left != null)
                preOrder.push(nowNode.left);
        }

        String midOrderString = "";
        nowNode = root;
        while (nowNode != null || !midOrder.isEmpty()) {
            while (nowNode != null) {
                midOrder.push(nowNode);
                nowNode = nowNode.left;
            }
            nowNode = midOrder.pop();
            midOrderString = midOrderString + nowNode.val + "-";
            nowNode = nowNode.right;
        }
        return preOrderString + midOrderString;
    }

    public static TreeNode deserialize(String data) {
        String[] numberString = data.split("-");
        int length = numberString.length / 2;
        int[] preOrder = new int[length];
        int[] midOrder = new int[length];
        for (int i = 0; i < length; i++) {
            preOrder[i] = Integer.valueOf(numberString[i]);
            midOrder[i] = Integer.valueOf(numberString[i + length]);
        }
        return buildTree(preOrder, midOrder);
    }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        int left = 0;
        int length = preorder.length;
        TreeNode root = new TreeNode(preorder[0] % 1024);
        for (int i = 0; i < length; i++) {
            if (inorder[i] == preorder[0]) {
                left = i;
                break;
            }
        }
        int[] newPre;
        int[] newIn;
        if (left != 0) {
            newPre = new int[left];
            newIn = new int[left];
            for (int i = 0; i < left; i++) {
                newPre[i] = preorder[i + 1];
                newIn[i] = inorder[i];
            }
            root.left = buildTree(newPre, newIn);
        }
        int rightSize = length - left - 1;
        if (rightSize != 0) {
            newPre = new int[rightSize];
            newIn = new int[rightSize];
            for (int i = 1; i <= rightSize; i++) {
                newPre[i - 1] = preorder[i + left];
                newIn[i - 1] = inorder[i + left];
            }
            root.right = buildTree(newPre, newIn);
        }
        return root;
    }
}
